package main.leetcode.offer.firstround.from03to50;

import java.util.Stack;

/**
 * 36.二叉搜索树与双向链表
 *
 * <p>输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
 * 特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
 */
public class ex36 { // Definition for a Node.
    private Node pre; // 前驱
    private Node head, tail;

    // 递归
    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        inOrder(root);
        head.left = tail;
        tail.right = head;
        return head;
    }

    private void inOrder(Node root) {
        if (root == null) return;
        inOrder(root.left);
        if (pre == null) head = root; // 遍历到最左，该节点为队首
        else pre.right = root; // 二叉搜索树的中序遍历输出本就是从小到大，因此前驱结点必定为该节点的前驱结点
        root.left = pre;
        pre = root;
        tail = root;
        inOrder(root.right);
    }

    // 非递归
    public Node treeToDoublyList1(Node root) {
        if (root == null) return null;
        Stack<Node> stack = new Stack<>();
        Node node = root;
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.add(node);
                node = node.left;
            }
            if (!stack.isEmpty()) {
                node = stack.pop();
                if (pre == null) head = node;
                else pre.right = node;
                node.left = pre;
                pre = node;
                tail = node;
                node = node.right;
            }
        }
        head.left = tail;
        tail.right = head;
        return head;
    }

    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }
}
